﻿using System;
using System.Collections.Generic;

using TracedReality.Primitive;
using TracedReality.RayTracing;

namespace TracedReality.SpatialTrees
{
    /// <summary>
    /// An octree implementation of a ShapeTree.
    /// </summary>
    public class ShapeOctTree : ShapeTree
    {
        /// <summary>
        /// An array of this node's children.
        /// </summary>
        private ShapeOctTree[] children;

        // <summary>
        /// Create a node with the given BoundingBox and depth.
        /// </summary>
        /// <param name="bb">BoundingBox that this node will contain.</param>
        /// <param name="dep">Depth of this node.</param>
        public ShapeOctTree(BoundingBox b, int d = 0)
        {
            bound = b;
            depth = d;
            shapes = new List<Shape>();
            children = null;
        }

        public override List<Shape> getAllShapes()
        {
            List<Shape> ashapes = new List<Shape>();
            ashapes.AddRange(shapes);
            if (children != null)
            {
                foreach (ShapeOctTree c in children) { ashapes.AddRange(c.getAllShapes()); }
            }

            return ashapes;
        }

        /// <summary>
        /// Check if this is a leaf node.
        /// </summary>
        /// <returns>True if this is a leaf node, false otherwise.</returns>
        public override bool isLeaf() { return children == null; }

        /// <summary>
        /// Get a count of how many Shapes are in this tree.
        /// </summary>
        /// <returns>How many Shapes are held in this tree.</returns>
        public override int getCount()
        {
            int count = shapes.Count;

            if (isLeaf()) { return count; }

            foreach (ShapeOctTree c in children) { count += c.getCount(); }

            return count;
        }

        /// <summary>
        /// Get the height of this tree.
        /// </summary>
        /// <returns>The height of the tree.</returns>
        public override int getHeight()
        {
            if (isLeaf()) { return 1; }

            int max = 0;
            foreach (ShapeOctTree c in children) { max = Math.Max(c.getHeight(), max); }

            return 1 + max;
        }

        /// <summary>
        /// Add a Shape to this tree.
        /// </summary>
        /// <param name="s">Shape to add.</param>
        public override void add(Shape s)
        {
            if (!overlaps(s.bound)) { return; }
            if (isLeaf()) { shapes.Add(s); return; }

            BoundingBox b = s.bound;
            int ct = 0;
            foreach (ShapeOctTree c in children) { if (c.overlaps(b)) { ct++; } }

            if (ct > 1) { shapes.Add(s); return; }

            foreach (ShapeOctTree c in children) { c.add(s); }
        }

        /// <summary>
        /// Use this tree to check of a Ray intersects anything before a given point.
        /// </summary>
        /// <param name="ray">Ray to cast</param>
        /// <param name="t">Distance to check against.</param>
        /// <returns>True if the Ray intersects something earlier, false otherwise.</returns>
        public override bool intersectAnythingBefore(Ray ray, double t)
        {
            Hit h = new Hit();
            h.t = t;
            if (!bound.intersects(ray, h)) { return false; }
            
            foreach (Shape s in shapes)
            {
                if (s.Intersect(ray, h) != 0)
                {
                    if (h.t < t) { return true; }
                }
            }

            if (isLeaf()) { return false; }

            foreach (ShapeOctTree c in children) { if (c.intersectAnythingBefore(ray, t)) { return true; } }

            return false;
        }

        /// <summary>
        /// Use this tree to cast a Ray and update a Hit.
        /// </summary>
        /// <param name="ray">Ray to cast.</param>
        /// <param name="hit">Hit to hold intersection information.</param>
        /// <returns>1 if the Ray intersects a Shape from the outside,
        /// -1 if the Ray intersects a Shape from the inside,
        /// and 0 if no intersection occurs.</returns>
        public override int castRay(Ray ray, Hit hit)
        {
            if (!bound.intersects(ray, hit)) { return 0; }

            int answer = 0;
            foreach (Shape s in shapes)
            {
                switch (s.Intersect(ray, hit))
                {
                    case 0:
                        break;
                    case 1:
                        answer = 1;
                        break;
                    case -1:
                        answer = -1;
                        break;
                }
            }

            if (isLeaf()) { return answer; }

            foreach (ShapeOctTree c in children)
            {
                switch (c.castRay(ray, hit))
                {
                    case 0:
                        break;
                    case 1:
                        answer = 1;
                        break;
                    case -1:
                        answer = -1;
                        break;
                }
            }

            return answer;
        }

        /// <summary>
        /// Split the current node if it is a leaf so that is contains no more than
        /// a given amount as long as it is above a given depth.
        /// </summary>
        /// <param name="maxcap">The maximum capacity of a node.</param>
        /// <param name="maxdep">The maximum depth of a node.</param>
        public override void split(int maxcap, int maxdep)
        {
            if (!isLeaf())
            {
                foreach (ShapeOctTree c in children) { c.split(maxcap, maxdep); }
                return;
            }
            if (depth >= maxdep) { return; }
            if (shapes.Count < maxcap) { return; }

            children = new ShapeOctTree[8];
            Vector diff = (bound.max - bound.min) / 2.0;
            for (int x = 0; x < 2; x++)
            {
                for (int y = 0; y < 2; y++)
                {
                    for (int z = 0; z < 2; z++)
                    {
                        int wh = (4 * x) + (2 * y) + z;
                        Vector xyz = new Vector(x, y, z);

                        Vector min = bound.min + (xyz * diff);
                        Vector max = bound.min + ((xyz + 1) * diff);
                        BoundingBox b = new BoundingBox(min, max);
                        children[wh] = new ShapeOctTree(b, depth + 1);
                    }
                }
            }

            List<Shape> oldlist = new List<Shape>(shapes);
            shapes = new List<Shape>();
            foreach (Shape s in oldlist) { add(s); }

            foreach (ShapeOctTree c in children) { c.split(maxcap, maxdep); }
        }

        public override void shrink()
        {
            List<BoundingBox> bbs = new List<BoundingBox>();
            if (!isLeaf())
            {
                foreach (ShapeOctTree c in children) { c.shrink(); bbs.Add(c.bound); }
            }

            foreach (Shape s in shapes) { bbs.Add(s.bound); }

            Vector center = bound.center;
            bound = BoundingBox.Minimum(bbs);

            if (bbs.Count == 0) { bound.translate(center); }
        }
    }
}
